2021 Algorithm                       < No.8 이상한 놈>                  Prof. Zoh Q.

2022 Algorithm                        < No.15 선착장>                       Prof. Zoh Q.

선착장

[문제]  어떤 무인도를 관광지로 개발하려고 한다. 이 섬에는 아직 배가 정박할 수 있는 선착장(marina)이 없어 이것부터 먼저 건설해야 이후 공사를 진행할 수 있다. 섬의 외각(contour)은 2차원 단순 다각형(simple polygon)으로 주어진다. 단순 다각형의 모든 변의 길이가 양수이며 인접하지 않는 변(edge)끼리는 교차하지 않는다. 그림-1에 단순 다각형과 아닌 경우가 제시되어 있다.

(a)                                           (b)

그림-1. 단순 다각형의 예(a)와 단순 다각형이 아닌 예(b)

이 문제에서 다각형의 [eqn: i]번째 꼭짓점은 [eqn: p _{i`} =(x_i``, y_i`)]으로 주어지며 모든 좌표는 양의 정수이다. 다각형의 경우 꼭짓점의 순서가 다각형의 모양을 결정하므로 이 순서가 중요하다. 이 문제에서 꼭짓점은 반시계방향으로 제시된다.

그런데 선착장은 꼭짓점에서 바다 쪽으로 보았을 때 180도 보다 작은 점(vertex)에서만 건설할 수 있다. 그림-2에서 주황색으로 표시된 점이 바로 그러한 위치다. 그래야만 열린 각도가 180도보다 큰 지점에 비하여 접안 시설의 건설비용을 줄일 수 있다. 단 [eqn: p _{8}]과 같이 그 각도가 180도 지점은 선택될 수 없다. 반드시 180도보다 커야 한다. 여러분은 섬 외곽을 표시한 단순 다각형에 관한 정보가 주어졌을 때 선착장이 될 수 있는 점의 위치를 오름차순으로 모두 출력해야 한다. 만일 그러한 지점이 하나도 존재하지 않는다면 숫자 0을 첫 줄에 출력해야 한다. 예를 들어, 섬이 정육각형 모양이라면 그런 선착장 후보지는 존재할 수 없다.

[입출력]   입력과 출력은 표준입출력을 사용한다. 첫 줄에 섬 외곽을 나타내는 다각형의 좌표 개수 [eqn: N]이 나오며, 다음 줄부터는 섬의 꼭짓점이 [eqn: p_1]부터 [eqn: p_N] 까지 순서대로 한 줄에 두 개의 정수 [eqn: x_i ```y_i]로 주어진다.

[예제1]

stdin	stdout
16 //[eqn: n] 4 1 6 2 8 3 7 4 //[eqn: p _{4}] 9 5 //[eqn: p _{5}] 10 1 14 5 13 8 12 11 11 8 //[eqn: p _{10}] 10 10 8 8 //[eqn: p _{12}] 5 11 1 8 4 7 //[eqn: p _{15}] 2 5	4 5 10 12 15

그림-2. 섬 지도에서 선착장을 만들 수 있는 꼭짓점
= { [eqn: p _{4}], [eqn: p _{5}], [eqn: p _{10}], [eqn: p _{12}], [eqn: p _{15}] }

[예제2]

stdin	stdout
15 //N 7 13 1 9 5 5 8 7 4 9 8 10 12 6 14 4 15 6 17 13 15 10 12 9 10 12 15 14 8 16 //[eqn: p_{15}]	1 5 6 11 12 13

[예제3]

stdin	stdout
15 //N 7 13 1 9 4 9 5 5 8 10 8 7 12 6 14 4 15 6 12 9 15 10 17 13 15 14 8 6 10 12 //[eqn: p_{15}]	3 5 7 10 15

[도움]   프로그램 이름은 marina.{c,cpp,py}. 동영상 강의 계산기하학에서 설명한 부호 면적(signed area)을 이용하면 쉽게 해결할 수 있다. 선분 [eqn: {vec{(p _{i-1}` ,`p _{i} )}}]의 기준에서 그다음 정점 [eqn: p_i+1]의 방향이 시계방향인지, 반시계방향인지를 확인하면 된다.